﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DataStuctureStudy.Trees
{
    class UnBalancedBinarySearchTree
    {
        public static void Test()
        {
            var tree = new Trees.UnBalancedBinarySearchTree.Tree<int>();
            tree.Insert(8);
            tree.Insert(4);
            tree.Insert(12);
            tree.Insert(2);
            tree.Insert(6);
            tree.Insert(10);
            tree.Insert(14);
            tree.Insert(1);
            tree.Insert(3);
            tree.Insert(5);
            tree.Insert(7);
            tree.Insert(9);
            tree.Insert(11);
            tree.Insert(13);
            tree.Insert(15);
            tree.Display();

            tree.Delete(3);
            tree.Display();

            tree.Delete(2);
            tree.Display();

            tree.Delete(5);
            tree.Display();

            tree.Delete(4);
            tree.Display();

            tree.Delete(12);
            tree.Display();
        }

        class Node<T>
            where T : IComparable<T>
        {
            public T Value { get; set; }

            public Node<T> Left { get; set; }

            public Node<T> Right { get; set; }

            public void InOrderTraverse(Action<T> action)
            {
                if (this.Left != null)
                {
                    this.Left.InOrderTraverse(action);
                }

                action(this.Value);

                if (this.Right != null)
                {
                    this.Right.InOrderTraverse(action);
                }
            }

            public int Depth()
            {
                var leftDepth = 0;
                var rightDepth = 0;

                if (this.Left != null)
                {
                    leftDepth = this.Left.Depth();
                }
                if (this.Right != null)
                {
                    rightDepth = this.Right.Depth();
                }

                return
                    leftDepth > rightDepth
                    ? leftDepth + 1
                    : rightDepth + 1;
            }
        }

        public class Tree<T>
             where T : IComparable<T>
        {
            private Node<T> Root { get; set; }

            public void Display()
            {
                Console.WriteLine();

                if (this.Root == null)
                {
                    return;
                }

                var depth = this.Root.Depth();
                var buffers = new string[depth][];
                for (int i = 0; i < buffers.Length; i++)
                {
                    buffers[i] = new string[(int)(Math.Pow(2, depth) - 1)];
                }

                this.BuildArray(this.Root, depth, buffers, 0, 0);

                for (int i = 0; i < buffers.Length; i++)
                {
                    for (int j = 0; j < buffers[i].Length; j++)
                    {
                        if (buffers[i][j] == null)
                        {
                            Console.Write(new string(' ', 5));
                        }
                        else
                        {
                            var leftPad = (5 - buffers[i][j].Length) / 2;
                            Console.Write(buffers[i][j]
                                .PadLeft(leftPad + buffers[i][j].Length)
                                .PadRight(5));
                        }
                    }
                    Console.WriteLine();
                    Console.WriteLine();
                }
            }

            private void BuildArray(Node<T> node, int nodeDepth, string[][] buffers, int row, int startColumn)
            {
                if (node == null)
                {
                    return;
                }

                var nodeWidth = Math.Pow(2, nodeDepth) - 1;
                var column = (int)(startColumn + nodeWidth / 2);

                buffers[row][column] = node.Value.ToString();

                this.BuildArray(node.Left, nodeDepth - 1, buffers, row + 1, startColumn);
                this.BuildArray(node.Right, nodeDepth - 1, buffers, row + 1, column + 1);
            }

            public bool Contains(T item)
            {
                var current = this.Root;

                while (current != null)
                {
                    if (item.CompareTo(current.Value) == 0)
                    {
                        return true;
                    }
                    else if (item.CompareTo(current.Value) < 0)
                    {
                        current = current.Left;
                    }
                    else
                    {
                        current = current.Right;
                    }
                }

                return false;
            }

            public void InOrderTraverse(Action<T> action)
            {
                if (this.Root != null)
                {
                    this.Root.InOrderTraverse(action);
                }
            }

            public void Insert(T item)
            {
                var node = new Node<T> { Value = item };

                Node<T> parent = null;
                var current = this.Root;
                var isLeft = false;

                while (current != null)
                {
                    parent = current;

                    if (item.CompareTo(current.Value) < 0)
                    {
                        current = current.Left;
                        isLeft = true;
                    }
                    else
                    {
                        current = current.Right;
                        isLeft = false;
                    }
                }

                if (parent == null)
                {
                    this.Root = node;
                }
                else if (isLeft)
                {
                    parent.Left = node;
                }
                else
                {
                    parent.Right = node;
                }
            }

            public bool Delete(T item)
            {
                Node<T> parent = null;
                var current = this.Root;
                var isLeft = false;

                this.Find(item, ref parent, ref current, ref isLeft);

                if (current == null)
                {
                    return false;
                }

                if (current.Right == null)
                {
                    if (parent == null)
                    {
                        this.Root = current.Left;
                    }
                    else if (isLeft)
                    {
                        parent.Left = current.Left;
                    }
                    else
                    {
                        parent.Right = current.Left;
                    }
                }
                else if (current.Right != null && current.Right.Left == null)
                {
                    current.Right.Left = current.Left;

                    if (parent == null)
                    {
                        this.Root = current.Right;
                    }
                    else if (isLeft)
                    {
                        parent.Left = current.Right;
                    }
                    else
                    {
                        parent.Right = current.Right;
                    }
                }
                else
                {
                    Node<T> currentRightSmallestParent = current.Right;
                    var currentRightSmallest = current.Right.Left;

                    this.FindSmallest(ref currentRightSmallestParent, ref currentRightSmallest);

                    currentRightSmallestParent.Left = currentRightSmallest.Right;
                    currentRightSmallest.Left = current.Left;
                    currentRightSmallest.Right = current.Right;
                    if (parent == null)
                    {
                        this.Root = currentRightSmallest;
                    }
                    else if (isLeft)
                    {
                        parent.Left = currentRightSmallest;
                    }
                    else
                    {
                        parent.Right = currentRightSmallest;
                    }
                }

                return true;
            }

            private void Find(T item, ref Node<T> parent, ref Node<T> current, ref bool isLeft)
            {
                while (current != null)
                {
                    if (item.CompareTo(current.Value) == 0)
                    {
                        break;
                    }

                    parent = current;

                    if (item.CompareTo(current.Value) < 0)
                    {
                        current = current.Left;
                        isLeft = true;
                    }
                    else
                    {
                        current = current.Right;
                        isLeft = false;
                    }
                }
            }

            private void FindSmallest(ref Node<T> parent, ref Node<T> current)
            {
                while (current != null)
                {
                    if (current.Left == null)
                    {
                        break;
                    }

                    parent = current;
                    current = current.Left;
                }
            }
        }
    }
}
